import com.hubu.util.ArrayUtils;
import java.util.Comparator;
public class QuickSort {
    public static<T> void sort(T array[], Comparator<T> comparator){
        quickSort(array,comparator,0,array.length-1);
    }
    public static<T> void sort(T array[]){
        quickSort(array,null,0,array.length-1);
    }
    public static <T> void quickSort(T array[],Comparator<T> comparator,int left,int right) {
        if (left >= right) {
            return;
        }
        int nextIndex = nextIndex(array, comparator, left, right);
        quickSort(array, comparator, left, nextIndex - 1);
        quickSort(array, comparator, nextIndex + 1, right);
    }
    public static<T> int nextIndex(T array[],Comparator<T> comparator,int left,int right){
        T value=array[left];
        int l=left;
        int r=right;
        while(l<r){
            while(l<r&&(compare(comparator,array[r],value)>0)){
                r--;
            }
            while(l<r&&(compare(comparator,array[l],value)<=0)){
                l++;
            }
            ArrayUtils.swap(array,l,r);
        }
        ArrayUtils.swap(array,left,r);
        return r;
    }
    public static <T>int compare(Comparator<T> comparator,T value1,T value2){
        return comparator!=null?comparator.compare(value1,value2):((Comparable)value1).compareTo(value2);
    }
}
